Prerequisite-free Set Theory: Just the Intuiton

"Today We Learned" series

Sudo Room

June 14 2014

[@notconfusing‽](http://twitter.com/notconfusing)

In [2]:
from IPython import display
In [7]:
display.Image('sets0.png')
Out[7]:
In [10]:
display.Image('sets01.png')
Out[10]:

References

  • Comic - "Logicomix - an Epic Search For Truth" Doxiadis, Papadimitiou - ISBN 978-1-59691-452-0
  • Book - "Set Theory and Logic" Robert R. Stoll - ISBN 0-486-63829-4

Origins

  • Set theory starts with Cantor (1845-1918)
    • Cantor needed a means of comparing the magnitude of infinite sets of numbers.
  • Reaction
    • Cantor's insistence was that infinite sets are on par with finite sets. This was an innovation.
    • Wasn't totally accepted at first.

Cantor's Concept of a Set

According to his definition:

a set \(S\) is any collection of definite, distinguishable objects of our intution or of our intellect to be conceived as a whole. The objects are called the elements or members of \(S\)

Is this really even a definition?

  • Firstly, this doesn't seem like a mathematical definition, it doesn't include any Math.
    • It's so fundamental, other concepts rest on it, and it has to be taken from our "intuition".
  • But we do this all the time in our language.
    • When we say "bunch," or "flock," or "heap," we are talking about sets.

It doesn't mention numbers.

In [3]:
display.Image('sets1.png')
Out[3]:
In [5]:
display.Image('sets2.png')
Out[5]:

If members of sets don't have do be numbers - what do they have to be?

Distinguishable

We have to able to say if two elements are the same.

  • This may seem odd, 4 is definitely 4.
  • But in the set of all feelings that occur on Saturdays, if I feel joyous two weeks in a row, is the way I'm feeling this Saturday the same as last Saturday?
    • The answer is not so important as us having a framework to answer it. Either, "yes, both were joyous feelings"; or "no, the feelings occured at different times," are valid answer-systems, so let us pick one and only one of them.

Definite

We have to be able to say definitely if a member is, or is not a member of a set.

  • In the set of all feelings that occur on Saturdays, is my hunger right now in the set?
    • Let us be sure we can answer this question with a firm "yes" or "no".
    • This is call a "set membership test", and it should always give either a "yes" or "no", but not "both", and not "neither".

Members don't have to be Exlpicit

  • For example answer to yourself - The set of all horses.
    • Are the elements:
      • Definite?
      • Distinguishable?

Members don't have to be Exlpicit

  • For example answer to yourself - The set of all horses.
    • Are the elements:
      • Definite?
        • Yes, I would say, we can denfinitely know when we are talking about the same horse or not.
      • Distinguishable?
        • Yes, I would say, we can determine with full accuracy what is, and what isn't a horse.

Implication of Definite, and Distinguishable

  • A set is completely determined by its members.
    • All a set is, is its members, and nothing else.

Notation

Speaking geek

Membership

\(x \in S\)

"x is an element of S"

or

\(x \notin S\)

"x is not an element of S"

Notation

Speaking geek

Defining a set

Explicit - enumerate the elements

\(S = \{1, 2, 3, 14\}\)

"S is the set with elements 1, and 2, 3, and fourteen"

Notation

Speaking geek

Defining a set

Predicate definition - you supply the variable and memebership test

\(S = \{x | x \text{ is even} \}\)

"The set of all numbers such that those numbers are even."

"The set of all even numbers"

\(S = \{\text{horse} | \text{horse has three legs} \}\)

"The set of all horses such that the horse has three legs".

"The set of all three-legged horeses."

Examples

  1. Is \(\{2, 4, 6\} = \{2, 4, 4, 6\}\)?

  2. Is \(\{2, 4, 6\} = \{6, 2, 4\}\)?

  3. Is \(\{\text{Morrissey}, \text{Bowie}\} = \{\{\text{Morrissey}, \text{Bowie}\}\} = \{\{\text{Bowie}\}, \{\text{Morissey}\}\}\) ?

Answers

  1. Is \(\{2, 4, 6\} = \{2, 4, 4, 6\}\)?
  • Yes. Duplicates don't count.
  1. Is \(\{2, 4, 6\} = \{6, 2, 4\}\)?
    • Yes, order doesn't count, we just care about what's in the or out of the set.
  2. Is \(\{\text{Morrissey}, \text{Bowie}\} = \{\{\text{Morrissey}, \text{Bowie}\}\} = \{\{\text{Bowie}\}, \{\text{Morissey}\}\}\) ?
    • No. The first one is the set of Morrissey and Bowie (the duet). The next os the set containing the duet. (the concept of the duet, my fantasy). The last is the set containing two sets, each of which Containg a singer (the concept of their solo careers).

The Empty Set

The set that contains no elements is the empty set.

Looks like: \(\emptyset\)

The Empty Set

Question is \(\emptyset = \{\emptyset\}\)?

No, but why?

Let's just think about the size of each set. On the left the size is zero, on the right the size is one.

The Set of all sets...

In [6]:
display.Image('sets3.png')
Out[6]:

The Yoga-Teacher Paradox

A big Math scandal, which temporarily destroyed set theory. I'll give my own reformulation as the Yoga Teacher Paradox, since the original version was needlessly male-oriented:

  1. Suppose there exists a village with just one Yoga Teacher.
  2. Everybody in the village does Yoga.
  3. For every person in the village they learn yoga in one of two ways.
    1. Everybody in the village either teaches themselves, or
    2. they are taught by the village yoga teacher.

Question: does the Yoga teacher, teach themselves?

  • Suppose the yoga teacher does teach themselves (point 3.A) . Then according to the rules they are not part of the villagers that are taught by the yoga teacher. But since they are the yoga teacher, they are being taught by the yoga teacher. This supposition cannot be true. Let's try the other one.
  • Suppose the yoga teacher is taught by the village yoga teacher (point 3.B). Then according to the rules they are not part of the villagers that teaches themselves. But since they are the yoga teacher, they are teaching themselves. This supposition cannot be true. Let's try another one. Oh wait there are no more suppositions. We've run into an impossible situation.

Conclusion

Set theory recovered from this problem by the creation of classes which are different from sets. But that's for another day.

Hopefully you get the idea that sets are basically minimal rigour to our basic understanding of what a collection of object is. It's so fundamental you actually don't need any Math for it, and in fact numbers are built on Set Theory.

Your homework is to use the concept of "empty set" in dinner time conversation.

In []: